Solving Multivariate Coppersmith Problems with Known Moduli

Abstract: A central problem in cryptanalysis involves computing the set of solutions within a bounded region to systems of modular multivariate polynomials. Typical approaches to this problem involve identifying shift polynomials, or polynomial combinations of input polynomials, with good computational properties. In particular, we care about the size of the support of the shift polynomials, the degree of each monomial in the support, and the magnitude of coefficients. While shift polynomials for systems of a single modular univariate polynomial have been well understood since Coppersmith's original 1996 work, multivariate systems have been more difficult to analyze. Most analyses of shift polynomials only apply to specific problem instances, and it has long been a goal to find a general method for constructing shift polynomials for any system of modular multivariate polynomials. In recent work, we have made progress toward this goal by applying Groebner bases, graph optimization algorithms, and Ehrhart's theory of polytopes to this problem. This talk focuses on these mathematical aspects as they relate to our work, as well as open conjectures about the asymptotic performance of our strategies.

number theory

Audience: researchers in the topic

Comments: pre-talk at 3pm

UCSD number theory seminar

Series comments: Most talks are preceded by a pre-talk for graduate students and postdocs. The pre-talks start 40 minutes prior to the posted time (usually at 1:20pm Pacific) and last about 30 minutes.